class Solution {
    public boolean exist(char[][] board, String word) {
        int h = board.length, w = board[0].length;
        boolean[][] visited = new boolean[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                boolean flag = check(board, visited, i, j, word, 0);
                if (flag) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 检查从board[i][j]出发，能否匹配到word[k:]
     * @param board
     * @param visited
     * @param i
     * @param j
     * @param s
     * @param k
     * @return
     */
    private boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
        
        
        if (board[i][j] != s.charAt(k)) { // 首字母不同，错
            return false;
        } else if (k == s.length() - 1) { // 字母相同且是最后一个字母，正确
            return true;
        }
        
        boolean result = false;
        // 已访问
        visited[i][j] = true;
        // 方向
        int[][] directions = {{0,1},{0,-1},{1,0},{-1,0}};
        for (int[] dir: directions){
            int newi = i+dir[0], newj = j+dir[1];
            // 合法方向
            if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
                if (!visited[newi][newj]) {
                    // 检查下一个
                    boolean flag = check(board, visited, newi, newj, s, k+1);
                    if (flag) {
                        result = true;
                        break;  // 正确则提前跳出剪枝
                    }
                }
            }
        }
        visited[i][j] = false; // 恢复访问列表
        return result;
    }
}